package 分治.归并排序;

import java.util.ArrayList;
import java.util.List;

public class 计算右侧小于当前元素的个数315 {
    int [] ret ; // 存储结果
    int [] index; // 存储原始索引
    int [] tmpindex; //中转
    int [] tmpNums; //中转值
   public List<Integer> countSmaller(int [] nums){
       int n = nums.length;
       ret = new int[n];
       index = new int[n];
       tmpindex = new int[n];
       tmpNums = new int[n];
       // 初始化index数组，保留元素的初始位置
       for(int i = 0 ;i<n ; i++)
           index[i] = i;

       mergeSort(nums,0,n-1);  // 归并排序

       List<Integer> L = new ArrayList<Integer>();
       for(int x:ret)
           L.add(x);

       return L;
   }
   public void mergeSort(int [] nums, int left, int right){
       if(left>=right)
           return ;

       int mid = (left+right)/2;
       mergeSort(nums,left,mid);
       mergeSort(nums,mid+1,right);
       int cur1 = left, cur2 = mid+1,i =  0;
       while(cur1<= mid && cur2 <= right){
           if(nums[cur1]<=nums[cur2])
           {
               tmpNums[i] = nums[cur2];
                tmpindex[i++] = index[cur2++]; //记录原始索引
           }
           else{
               ret[index[cur1]] += right-cur2+1; //右侧有几个小于当前元素的个数
               tmpNums[i] = nums[cur1];
               tmpindex[i++] = index[cur1++];
           }
       }

       while(cur1<=mid)
       {
           tmpNums[i] = nums[cur1];
           tmpindex[i++] = index[cur1++];
       }
       while (cur2<=right)
       {
           tmpNums[i] = nums[cur2];
           tmpindex[i++] = index[cur2++];
       }
       for(int m = left;m<=right ; m++){
           // tmpNum,tmpindex 是存储合并后的结果，合并完成后需要将临时数组中的结果复制回原数组nums，index
           // 来保持原数组的数据是已排序的，同时确保索引数组index也保持同步更新
           nums[m] = tmpNums[m-left];
           index[m] = tmpindex[m-left];
       }//确保原始数组与索引为最新排序状态，可以正确计算每个元素右侧小于它的元素个数

   }


}
